A video stream comprises of a plurality of frames/images that comprise a substantial amount of data. To increase the efficiency of a video system, a video that needs to be transmitted or stored is digitally compressed by removing redundancies from images. Digital compression reduces the number of bits needed to represent the video while maintaining quality of the video. The reduction in bits allows more efficient use of channel bandwidth and reduces storage requirements. In a video stream there may exist certain blocks of pixels that are temporarily redundant. To take advantage of temporal redundancy in the video, “motion compensation” technique is utilized. Motion compensation technique is often employed in connection with digital compression of a video stream. The basic idea of motion estimation is to look for a block of pixels in a current frame that is same or nearly the same as portions of previous frames, although in different positions because the subject of the frame has moved. If such a block of similar pixels is found, then the system only needs to transmit a code that tells the reconstruction end of the system where to find the needed pixels in a previously received frame. Thus motion estimation is the task of finding predictive blocks of image pixels within reference frames that best match a similar-sized block of pixels in the current frame.
The displacement between the currently-coded block and the best matching block in the previous frame is indicated by a “motion vector”, which is the result produced by the motion estimation process. The motion vector is transmitted along with the transformed, quantized, reordered, entropy-encoded difference information for the current block. The motion compensation allows for a minimization of the differences between the current pixel block and the reference block, so that the amount of data required to be transmitted/recorded can be minimized. Motion compensation is a key component of video coding technologies, and is one of the most computationally complex processes within a video encoding system. An issue that arises with motion-compensated video compression-coding is the amount of processing required for the coding. Motion estimation may comprise a significant part of the processing burden, particularly when a so-called “full search” algorithm is employed.
The enormous technological enhancements for accessing video content through smart phones, tabs and mobiles phones from the past few decades drove many of the video coding standards to produce good quality stream with low bitrates. The high compression performance may be achieved by using video coding standards such as High Efficiency Video Coding (HEVC), H.264/MPEG-AVC and MPEG4 where temporal redundancy that can be notably reduced using inter frame prediction. The inter frame prediction is done by using a block matching algorithm, which performs the motion estimation of macro blocks between the frames. Specifically, HEVC is said to double the data compression ratio compared to H.264/MPEG-4 at the same level of video quality. It can alternatively be used to provide substantially improved video quality at the same bit rate. HEVC replaces 16×16 pixel macro blocks which were used with previous standards with coding tree units (CTUs) which can use larger block structures of up to 64×64 samples and can better sub-partition the picture into variable sized structures. This, however, has led to the dramatic increase in computational complexity, as an instance, HEVC standard supports very high resolution videos up to 4K (3840×2160 pixels) and 8K (7680×4320 pixels) dividing each image into coding tree units and each coding tree units into 4×4 to 64×64 block pixels. The Coding Tree Unit (CTU) or coding block based search algorithm used for motion estimation in HEVC achieves higher compression performance than existing video coding standards such as H.264/AVC, MPEG-series, but with huge computational complexity.
A number of methods for reducing the complexity have been provided till now, however, each method has its drawbacks. In one method, the search is chosen by predicting the movements of the same objects by constructing depth maps at some constant regular intervals. However, the method does not concentrate on varying the search patterns based on the created depth maps on a frame level or block level. In another method, adaptive search patterns are utilized that are based on the motion content in the video using Error Descent Rate (EDR) calculation. This method however, does not concentrate on the motion present in the video or scene cut details or previous error residual of the frames. Also, this is not fit for the video flows which have variable bandwidth at each link in a wireless network. In another method, the efficient content based algorithm is proposed using temporal redundancy (TRA) approach by choosing the search pattern dynamically with optimized adaptive search range. In all of these algorithms, the search range or search patterns are selected adaptively based on the motion content without having the knowledge of the network which receives the encoded bit stream.
In most of the real time video streaming applications, it is impossible to know the motion present in the video before the video flow is started. Hence most of the existing motion estimation algorithms have fixed search pattern selected at the starting of the flow. This, however, can lead to improper selection of search algorithm in the case of video flows across a wireless networks with dynamic bandwidth capability, though there is a provision for estimating available bandwidth for a link at each node in the network. Moreover, the calculation to be performed in techniques such as ITU-T H.264/ISO MPEG-4 AVC based encoder, increases manifolds considering that motion estimation may need to be performed using multiple references or block sizes. It is therefore highly desirable to consider fast motion estimation strategies so as to reduce encoding complexity while simultaneously having minimal impact on compression efficiency and quality. Further, the non deterministic bandwidth allocation in wireless mobile ad hoc networks will have huge impact in video flows using such coding standards.
Hence, there exists a need for a method for dynamically selecting an efficient block matching algorithm based on video content and the available bandwidth. There is also a need for a method for detecting the variance of motion in the video based on the temporal redundancy achieved for reducing the number of candidate macro blocks that need to be searched in the reference frames. Moreover, there is a need to optimize the motion estimation in video coding at the application level balancing the Quality of Service at the network layer in video flows over wireless networks.